package array

// 和为s的两个数
// 输入一个 递增的 排序数组 和一个数字s  在数组汇总查找两个数，它们之和刚好是s
// 如果有多对结果则返回任意一对即可

// 双指针解法 时间复杂度on  空间复杂度o1
// 数组是递增的

func TwoSum(nums []int, target int) []int {
	// 当双指针相遇时退出
	// 若s>target 指针j向左移动
	// 若s<target 指针向右移动
	// 若s=target 立即返回i,j位置的值
	i, j := 0, len(nums)-1
	for i < j {
		s := nums[i] + nums[j]
		if s < target {
			i++
		} else if s > target {
			j--
		} else {
			return []int{nums[i], nums[j]}
		}
	}
	return nil
}

// map解法 时间复杂度on  空间复杂度o1
// 这种解法不需要要求数组是递增的

func TwoSumOfDict(nums []int, target int) []int {
	dict := make(map[int]int)
	for idx, _ := range nums {
		if v, ok := dict[target-nums[idx]]; ok {
			return []int{v, idx}
		} else {
			dict[nums[idx]] = idx
		}
	}
	return []int{}
}
